package binarysearch

// 给定一个按照升序排列的整数数组 nums，和一个目标值 target。
// 找出给定目标值在数组中的开始位置和结束位置。
// 如果数组中不存在目标值 target，返回 [-1, -1]。
// 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
func searchRange(nums []int, target int) []int {
	if len(nums) == 0 {
		return []int{-1,-1}
	}
	left,right := 0,len(nums)-1
	leftBorder,rightBorder := -2,-2
	leftBorder,rightBorder = getLeftBorder(nums,left,right,target),getRightBorder(nums,left,right,target)
	
	// 分析三种情况
	// 情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返回{-1, -1}
	if leftBorder==-2 || rightBorder==-2{
		return []int{-1,-1}
	}
	// 情况三：target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}
	if rightBorder-leftBorder>1 {
		return []int{leftBorder+1,rightBorder-1}
	}
	// 情况二：target 在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1}
	return []int{-1,-1}
}
func getRightBorder(nums []int, left,right,target int) int {
	var rightBorder int = -2
	for left<=right {
		mid := left + (right-left)/2
		if nums[mid] > target { // 左边继续
			right = mid - 1
		}else {
			left = mid+1   
			rightBorder = left  // 在右侧寻找右边界 
		}
	}
	return rightBorder
}
func getLeftBorder(nums []int, left,right,target int) int {
	var leftBorder int = -2
	for left<=right {
		mid := left + (right-left)/2
		if nums[mid] < target { // 
			left = mid + 1
		}else {
			right = mid-1 
			leftBorder = right  // 在左侧寻找左边界 
		}
	}
	return leftBorder
}
